1. Field of the Invention
This invention relates generally to computer systems and more specifically to garbage collection memory management on a digital computer system.
2. Description of the Related Art
Garbage collection is the memory management technique of choice on symbolic computing systems. This is true on standard architecture machines running languages such as LISP as well as on dedicated LISP processors such as the Explorer from Texas Instruments. Garbage collection is oriented toward use with a dynamic memory containing a multitude of objects linked by pointers.
Garbage collection is the process of allocating new memory objects and returning to available memory those which can no longer be accessed. Computer systems which are not dedicated to running symbolic languages such as LISP generally utilize what is known as a stop and collect garbage collector. This operates by, when garbage collection becomes necessary, causing all normal operations to cease. The garbage collector then traces pointers from accessible objects to find all other accessible objects. Accessible objects are copied to a special location so they can be saved. The location for objects to be saved is called newspace, while the portion of virtual memory being collected is called oldspace. When all accessible objects have been copied, all of the memory in oldspace is freed for use by the system.
This type of memory management technique has a severe drawback in that the time required for the garbage collection process can be very long. Collection times of up to one hour are common in moderately large virtual memory spaces of several tens of megabytes. Garbage collection takes longer on larger virtual memories so that the delays necessary to collect the very large memories which are expected to exist on machines of the future will become interminable with the stop and collect process.
Systems which are dedicated to running LISP-like languages usually utilize a garbage collection technique known as incremental garbage collection. The general idea behind these techniques is to operate the garbage collector as a process concurrent with normal system activities. Garbage is reclaimed in small amounts over a period of time, ideally without unduly degrading the overall system performance.
Concurrent garbage collection techniques are more complex than the stop and copy technique, because care must be taken that the collector does not change pointers or move objects in such a way that the normal system functions are disrupted. Also, the normal system functions must not interfere with the operations of the collector. Concurrent systems have several rules regarding what can be done with various pointers stored in different logical spaces within the virtual address space, and these rules must be strictly observed at all times by the collector and normal system processes.
One result of these types of memory management techniques is that the virtual memory space tends to be filled with a very large number of very small objects. The average object size is typically about 25 bytes. This results in many small blocks being scattered around the very large virtual memory space. Since the amount of main memory in most systems is generally substantially smaller than virtual memory, it is necessary to swap memory pages between the main memory and the backing store, usually a hard disk, at a high rate. This paging upon a virtual memory fault is extremely time consuming.
The bandwidth of usable memory which can be paged to and from the disk is often the limiting factor in overall system performance. While the raw rate of information transfer to and from most disks is fairly high, the useful rate of transfer is often quite low. This can occur for several reasons. First, if the garbage collection process is not performed in a timely fashion, garbage objects tend to become intermixed with non-garbage objects. When this occurs it is not possible to transfer useful (non-garbage) objects to main memory without also transferring useless (garbage) objects. A procedure for timely collection of garbage is described in copending U.S. Pat. No. 4,807,120, titled TEMPORAL GARBAGE COLLECTOR WITH INDIRECTION CELLS, by Courts, assigned to the assignee of the present application, which application is hereby incorporated by reference in its entirety.
However, even when all true garbage is collected in a timely fashion, one can still have a very low rate of access to useful information if small objects of interest are located in the virtual address space intermixed with other objects which are not of interest at the same time. In large virtual address space systems it is quite common for the total size of all objects of interest over a period of time to be a small percentage of the total size of all objects which can be accessed. If this percentage is 10%, for example, and the objects of interest are uniformly intermixed with other objects not of interest, then the rate of useful information transfer from disk is only 10% of the raw transfer rate. Also, it takes 10 times as much main memory to hold a working set as would be required if it were possible to access only the useful information.
It is clearly desirable for a memory management system to arrange the placement of objects in the virtual address space such that it is very likely that if an object is needed then the other objects placed near it will also be needed at the same time. Such an object placement will increase the useful rate of information transfer from disk and also reduce the size of main memory required to hold a working set.